#include "functionlist.h"

// Função que conta a quantidade de algarismos de um número:
unsigned int algs(unsigned int n)
{
    n /= 10;
    if (n == 0) return(1);
    return(1+algs(n));
}

argumentos recursao_F_args(argumentos a)
{
    argumentos args = argumentos_novo(a.tamanho-1,false);
    if (args.tamanho) memcpy(args.elementos,a.elementos,args.tamanho*sizeof(VALORES_TIPO));
    return(args);
}

argumentos recursao_H_args(argumentos a)
{
    argumentos args = argumentos_copia(a);
    if (args.tamanho) args.elementos[args.tamanho-1]--;
    return(args);
}

argumentos recursao_G_args(argumentos a, VALORES_TIPO H_resultado)
{
    argumentos args = argumentos_novo(a.tamanho+1,false);
    if (args.tamanho)
    {
        args.elementos[0] = a.elementos[a.tamanho-1]-1;
        args.elementos[1] = H_resultado;
        unsigned int i;
        for (i=2 ; i<args.tamanho ; i++) args.elementos[i] = a.elementos[i-2];
    }
    return(args);
}

/// *** Funções sobre os nós da lista encadeada: [INÍCIO] **********************************************
NOfundef* fundef_novo(const char *n, const char *v)
{
    NOfundef* no = (NOfundef*)malloc(sizeof(NOfundef));
    if (no)
    {
        no->primitiva = false;
        no->nome = NULL;
        no->variaveis = NULL;
        no->implementacao.tipo = -1;
        no->implementacao.impl = NULL;
        no->prox = NULL;
        setstring(&(no->nome),n);
        setstring(&(no->variaveis),v);
    }
    return(no);
}

NOfundef* fundef_primitiva_novo(const char *n, funtipo t)
{
    NOfundef* no = fundef_novo(n,NULL);
    if (no)
    {
        no->primitiva = true;
        no->implementacao.tipo = t;
    }
    return(no);
}

void fundef_del(NOfundef *no)
{
    if (!no) return;
    free(no->nome);
    free(no->variaveis);
    funimpl_del(no->implementacao);
    free(no);
}

void fundef_print(NOfundef *no, unsigned int recuo)
{
    if (!no) return;
#ifdef DEBUG_FUNDEF_PRINT
    printf("{%p} (%s) ",no,get_tipo_nome(no->implementacao.tipo));
#endif //DEBUG_FUNDEF_PRINT
    if (no->primitiva)
    {
        switch (no->implementacao.tipo)
        {
        case GENERAL_FUNCTION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            return;
        }
        case ZERO_FUNCTION:
        {
            printf("%s(x) = 0",no->nome);
            break;
        }
        case SUCCESSOR_FUNCTION:
        {
            printf("%s(x) = x + 1",no->nome);
            break;
        }
        case PROJECTION_FUNCTION:
        {
            printf("%s_i_n(x1,...,xn) = xi",no->nome);
            break;
        }
        case CONSTANT_FUNCTION:
        {
            printf("%s(x) = k",no->nome);
            break;
        }
        case COMPOSITION_OPERATION:
        {
            printf("[operacao]\n");
            printf("%*sH(x1,...,xn) = F(G1(x1,...,xn),...,Gk(x1,...,xn))",recuo," ");
            break;
        }
        case RECURSION_OPERATION:
        {
            printf("[operacao]\n");
            printf("%*sH(x1,...,xn,0)   = F(x1,...,xn)\n",recuo," ");
            printf("%*sH(x1,...,xn,t+1) = G(t,H(x1,...,xn,t),x1,...,xn)",recuo," ");
            break;
        }
        default:
        {
            ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
            return;
        }
        }
#ifdef DEBUG_FUNDEF_PRINT
        printf(" {-}");
#endif //DEBUG_FUNDEF_PRINT
    }
    else
    {
        switch (no->implementacao.tipo)
        {
        case GENERAL_FUNCTION:
        case ZERO_FUNCTION:
        case SUCCESSOR_FUNCTION:
        case PROJECTION_FUNCTION:
        case CONSTANT_FUNCTION:
        {
            printf("%s(",no->nome);
            var_print(no->variaveis);
            printf(") = ");
            funimpl_print(no->implementacao);
#ifdef DEBUG_FUNDEF_PRINT
            printf(" {%p}",funimpl_get_definicao(no->implementacao));
#endif //DEBUG_FUNDEF_PRINT
            break;
        }
        case COMPOSITION_OPERATION:
        {
            printf("%s(",no->nome);
            var_print(no->variaveis);
            printf(") = ");
            funimpl_print(no->implementacao);
#ifdef DEBUG_FUNDEF_PRINT
            compositionimpl *impl = (compositionimpl*)no->implementacao.impl;
            // Exibir o ponteiro definição da função EXTERNA:
            printf(" {%p}(",funimpl_get_definicao(impl->externa));
            // Exibir o ponteiro definição de cada função INTERNA:
            if (impl->internas_quant)
            {
                unsigned int i;
                printf("{%p}",funimpl_get_definicao(impl->internas[0]));
                for (i=1 ; i<impl->internas_quant ; i++) printf(",{%p}",funimpl_get_definicao(impl->internas[i]));
            }
            printf(")");
#endif //DEBUG_FUNDEF_PRINT
            break;
        }
        case RECURSION_OPERATION:
        {
            recursionimpl *impl = (recursionimpl*)no->implementacao.impl;
#ifdef DEBUG_FUNDEF_PRINT
            // Exibir o ponteiro que será usado para executar o loop da recursão:
            printf("{%p}",impl->recursao);
            // Exibir o caso base da recursão:
            printf("\n%*s",recuo," ");
#endif //DEBUG_FUNDEF_PRINT
            recursao_print(no->nome,no->variaveis,RECURSAO_BASE);
            printf("   = ");
            funimpl_print(impl->base);
#ifdef DEBUG_FUNDEF_PRINT
            printf(" {%p}",funimpl_get_definicao(impl->base));
#endif //DEBUG_FUNDEF_PRINT
            // Exibir o passo da recursão:
            printf("\n%*s",recuo," ");
            recursao_print(no->nome,no->variaveis,RECURSAO_PASSO);
            printf(" = %s(",funimpl_get_nome(impl->passo));
            const char *v = funimpl_get_variaveis(impl->passo);
            if (v && (strlen(v) >= 2))
            {
                printf("%c,",*v);
                v++;
                recursao_print(no->nome,no->variaveis,RECURSAO_DEFINICAO);
                v++;
                while(*v)
                {
                    printf(",%c",*v);
                    v++;
                }
            }
            printf(")");
#ifdef DEBUG_FUNDEF_PRINT
            printf(" {%p}",funimpl_get_definicao(impl->passo));
#endif //DEBUG_FUNDEF_PRINT
            break;
        }
        default:
        {
            ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
            return;
        }
        }
    }
}

unsigned int fundef_aridade(NOfundef *no)
{
    if (!no) return(0);
    if (no->primitiva)
    {
        switch (no->implementacao.tipo)
        {
        case GENERAL_FUNCTION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        case ZERO_FUNCTION:
        case SUCCESSOR_FUNCTION:
            return(1);
        case PROJECTION_FUNCTION:
        case CONSTANT_FUNCTION:
        case COMPOSITION_OPERATION:
        case RECURSION_OPERATION:
            break;
        default:
            ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
        }
    }
    else if (no->variaveis) return(strlen(no->variaveis));
    return(0);
}

VALORES_TIPO fundef_eval(NOfundef *no, argumentos args)
{
    linkedlist_init(&pilhaargs,NO_ARGS);
    semmemoria = false;
    VALORES_TIPO resultado = fundef_eval_start(no,args,0);
    linkedlist_clear(&pilhaargs);
    return(resultado);
}

VALORES_TIPO fundef_eval_start(NOfundef *no, argumentos args, unsigned int Ui)
{
    if (semmemoria) return(0);
    if (!no)
    {
#ifdef DEBUG_FUNCTIONLIST_EVAL
        printf(">>> %s(): chamada com no nulo. Abortar!\n",__FUNCTION__);
#endif //DEBUG_FUNCTIONLIST_EVAL
        return(0);
    }
    if (!args.tamanho)
    {
        ERRO_ARGUMENTOS_VAZIOS(__FUNCTION__);
        return(0);
    }
    unsigned int aridade = fundef_aridade(no);
#ifdef DEBUG_FUNCTIONLIST_EVAL
    printf(">>> %s(): ",__FUNCTION__);
    if (no->primitiva) printf("[folha] ");
    printf("%s",no->nome);
    if(Ui) printf(".%u.%u",Ui,args.tamanho);
    printf("(");
    argumentos_print(args);
    printf(") / tipo: %s / ari: %u ...\n",get_tipo_nome(no->implementacao.tipo),aridade);
#endif //DEBUG_FUNCTIONLIST_EVAL
    // Checar se o nó tem a flag "primitiva" (ou seja, ele é uma "folha" e fim da recursão):
    if (no->primitiva)
    {
        switch (no->implementacao.tipo)
        {
        case GENERAL_FUNCTION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        case ZERO_FUNCTION:
        {
            if (aridade == args.tamanho) return(0);
            ERRO_ARGUMENTOS_ARIDADE(__FUNCTION__,args.tamanho,aridade);
            break;
        }
        case SUCCESSOR_FUNCTION:
        {
            if (aridade == args.tamanho) return(args.elementos[0] + 1);
            ERRO_ARGUMENTOS_ARIDADE(__FUNCTION__,args.tamanho,aridade);
            break;
        }
        case PROJECTION_FUNCTION:
        {
            if ((Ui >= 1) && (Ui <= args.tamanho)) return(args.elementos[Ui-1]);
            ERRO_PROJECAO_LIMITE(__FUNCTION__,Ui,args.tamanho);
            break;
        }
        case CONSTANT_FUNCTION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        case COMPOSITION_OPERATION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        case RECURSION_OPERATION:
        {
            ERRO_PRIMITIVA_INCORRETA(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        default:
            ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
        }
    }
    else if (!(no->implementacao.impl))
        ERRO_IMPLEMENTACAO_NULA(__FUNCTION__,no->nome);
    else
    {
        switch (no->implementacao.tipo)
        {
        case GENERAL_FUNCTION:
        case ZERO_FUNCTION:
        case SUCCESSOR_FUNCTION:
        case PROJECTION_FUNCTION:
            return(fundef_eval_start(funimpl_get_definicao(no->implementacao),args,funimpl_get_indice(no->implementacao)));
        case CONSTANT_FUNCTION:
        {
            ERRO_TIPO_INCORRETO(__FUNCTION__,no->implementacao.tipo);
            break;
        }
        case COMPOSITION_OPERATION:
        {
            compositionimpl *impl = (compositionimpl*)no->implementacao.impl;
            // Uma pequena otimização: se a função EXTERNA for uma Função Projeção,
            // então avalia apenas a função INTERNA indicada pelo índice da projeção:
            unsigned int indice = funimpl_get_indice(impl->externa);
            if (indice)
            {
                if (indice > impl->internas_quant)
                {
                    ERRO_PROJECAO_LIMITE(__FUNCTION__,indice,impl->internas_quant);
                    break;
                }
                indice--;
                return(fundef_eval_start(funimpl_get_definicao(impl->internas[indice]),args,funimpl_get_indice(impl->internas[indice])));
            }
            // Vetor para armazenar o retorno de todas as funções internas
            // (será o argumento de entrada para a função externa):
            argumentos args_aux = argumentos_novo(impl->internas_quant,false);
            if (!args_aux.tamanho)
            {
                semmemoria = true;
                break;
            }
            linkedlist_push_args(&pilhaargs,args_aux);
            return(fundef_eval_composition(0,impl->internas,args,impl->externa,args_aux));
        }
        case RECURSION_OPERATION:
        {
            recursionimpl *impl = (recursionimpl*)no->implementacao.impl;
            /// Se o argumento mais a direita (variável da recursão) de "args"
            /// for zero, então aplicar "args" na BASE da recursão (F):
            /// ****************************************
            /// * > H(0) = k                           *
            /// *   OU                                 *
            /// * > H(x1, ..., xn, 0) = F(x1, ..., xn) *
            /// ****************************************
            if (args.elementos[args.tamanho-1] == 0)
            {
                // Se a aridade for 1, então a base da recursão deve ser uma constante:
                if (aridade == 1)
                    return(funimpl_get_constante(impl->base));
                else
                {
                    argumentos args_aux = recursao_F_args(args);
                    if (!args_aux.tamanho)
                    {
                        semmemoria = true;
                        break;
                    }
                    linkedlist_push_args(&pilhaargs,args_aux);
                    return(fundef_eval_start(funimpl_get_definicao(impl->base),args_aux,funimpl_get_indice(impl->base)));
                }
            }
            /// Senão, aplicar "args" no PASSO da recursão (G):
            /// ****************************************************************
            /// * > H(t+1) = G(t, H(t))                                        *
            /// *   OU                                                         *
            /// * > H(x1, ..., xn, t+1) = G(t, H(x1, ..., xn, t), x1, ..., xn) *
            /// ****************************************************************
            else
            {
                if (args.tamanho+1 > VALORES_TAMANHO)
                {
                    ERRO_ARGUMENTOS_EXTRAPOLOU(__FUNCTION__,args.tamanho+1,VALORES_TAMANHO);
                    break;
                }
                // Uma pequena otimização: se a função PASSO for uma Função Projeção,
                // então avalia apenas o elemento indicado pelo índice da projeção:
                unsigned int indice = funimpl_get_indice(impl->passo);
                if (indice)
                {
                    if (indice > funimpl_aridade(impl->passo))
                    {
                        ERRO_PROJECAO_LIMITE(__FUNCTION__,indice,funimpl_aridade(impl->passo));
                        break;
                    }
                    indice--;
                    switch(indice)
                    {
                    case 0:
                        return(args.elementos[args.tamanho-1]-1);
                    case 1:
                    {
                        argumentos args_aux = recursao_H_args(args);
                        if (!args_aux.tamanho)
                        {
                            semmemoria = true;
                            return(0);
                        }
                        linkedlist_push_args(&pilhaargs,args_aux);
                        return(fundef_eval_start(impl->recursao,args_aux,0));
                    }
                    default:
                        return(args.elementos[indice-2]);
                    }
                }
                // Vetor para os argumentos de H:
                argumentos args_aux = recursao_H_args(args);
                if (!args_aux.tamanho)
                {
                    semmemoria = true;
                    break;
                }
                // Aplicar o vetor de argumentos "args_aux" em H:
                VALORES_TIPO resultado = fundef_eval_start(impl->recursao,args_aux,0);
                // Reusar o vetor para os argumentos de G:
                argumentos_del(args_aux);
                args_aux = recursao_G_args(args,resultado);
                if (!args_aux.tamanho)
                {
                    semmemoria = true;
                    break;
                }
                // Aplicar o vetor de argumentos "args_aux" em G e retornar:
                linkedlist_push_args(&pilhaargs,args_aux);
                return(fundef_eval_start(funimpl_get_definicao(impl->passo),args_aux,funimpl_get_indice(impl->passo)));
            }
            break;
        }
        default:
            ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
        }
    }
    return(0);
}

VALORES_TIPO fundef_eval_composition(unsigned int passo, funimpl *internas, argumentos internas_args, funimpl externa, argumentos externa_args)
{
    if (semmemoria) return(0);
    if (passo >= externa_args.tamanho) return(fundef_eval_start(funimpl_get_definicao(externa),externa_args,funimpl_get_indice(externa)));
    externa_args.elementos[passo] = fundef_eval_start(funimpl_get_definicao(internas[passo]),internas_args,funimpl_get_indice(internas[passo]));
    return(fundef_eval_composition(passo+1,internas,internas_args,externa,externa_args));
}
/// *** Funções sobre os nós da lista encadeada: [FIM] *************************************************

/// *** Funções sobre a cabeça da lista encadeada: [INÍCIO] ********************************************
void funlista_init(funlista *fl)
{
    if (!fl) return;
    fl->inicio = NULL;
    fl->fim = NULL;
    fl->tamanho = 0;
}

void funlista_clear(funlista *fl)
{
    if (!fl) return;
    while(fl->inicio)
    {
        fl->fim = fl->inicio;
        fl->inicio = fl->inicio->prox;
        fundef_del(fl->fim);
    }
    fl->fim = NULL;
    fl->tamanho = 0;
}

void funlista_add(funlista *fl, NOfundef *no)
{
    if (!fl || !no) return;
    if (!fl->inicio)
        fl->inicio = no;
    else
        fl->fim->prox = no;
    fl->fim = no;
    fl->tamanho++;
}

NOfundef* funlista_add_primitivas(funlista *fl)
{
    if (!fl) return(NULL);
    funlista_clear(fl);
    funlista_add(fl,fundef_primitiva_novo("Z",ZERO_FUNCTION));
    funlista_add(fl,fundef_primitiva_novo("S",SUCCESSOR_FUNCTION));
    NOfundef *proj = fundef_primitiva_novo("U",PROJECTION_FUNCTION);
    funlista_add(fl,proj);
    funlista_add(fl,fundef_primitiva_novo(NULL,COMPOSITION_OPERATION));
    funlista_add(fl,fundef_primitiva_novo(NULL,RECURSION_OPERATION));
    return(proj);
}

void funlista_print(funlista *fl)
{
    if (!fl) return;
    unsigned int i = 0;
    unsigned int recuo = algs(fl->tamanho);
    NOfundef *p = fl->inicio;
    while(p)
    {
        printf(" %*u. ",recuo,++i);
        fundef_print(p,recuo+3);
        printf("\n");
        p = p->prox;
    }
}

NOfundef* funlista_search(funlista *fl, const char *n, unsigned int a)
{
    if (!fl || !n) return(NULL);
    NOfundef *p = fl->inicio;
    while(p)
    {
        // Checar se os nomes das funções são iguais:
        if ((p->nome) && (!strcmp(p->nome,n)))
        {
            // Caso os nomes das funções sejam iguais e "a" zero, então achou o nó.
            // (ou seja, "casa" apenas os nomes das funções!)
            if (a == 0) break;
            // Se "a" for não nulo, comparar o valor dele com a aridade do nó atual.
            // (ou seja, "casa" os nomes das funções E as aridades delas!)
            else if (fundef_aridade(p) == a) break;
        }
        p = p->prox;
    }
    return(p);
}

bool funlista_definir(funlista *fl, NOfundef *no)
{
    if (!fl || !no || no->primitiva) return(false);
    // O próximo erro nunca ocorrerá, pois o parser já deve
    // ter se assegurado que o "no" tenha uma implementação:
    if (!no->implementacao.impl)
    {
        ERRO_IMPLEMENTACAO_NULA(__FUNCTION__,no->nome);
        return(false);
    }
    // Variáveis para guardar os dados da implementação do "no":
    char         projecao_nome[]  = "U";
    const char*  fi_nome          = funimpl_get_nome(no->implementacao);
    unsigned int fi_aridade       = funimpl_aridade(no->implementacao);
    NOfundef**   ptr_fi_definicao = NULL;
    // Pegar o nome e a referencia ao ponteiro "definicao" da implementação do "no":
    switch (no->implementacao.tipo)
    {
    case GENERAL_FUNCTION:
    {
        generalimpl *impl = (generalimpl*)no->implementacao.impl;
        ptr_fi_definicao = &(impl->definicao);
        break;
    }
    case ZERO_FUNCTION:
    {
        zeroimpl *impl = (zeroimpl*)no->implementacao.impl;
        ptr_fi_definicao = &(impl->definicao);
        break;
    }
    case SUCCESSOR_FUNCTION:
    {
        successorimpl *impl = (successorimpl*)no->implementacao.impl;
        ptr_fi_definicao = &(impl->definicao);
        break;
    }
    case PROJECTION_FUNCTION:
    {
        projectionimpl *impl = (projectionimpl*)no->implementacao.impl;
        ptr_fi_definicao = &(impl->definicao);
        fi_nome = projecao_nome;
        fi_aridade = 0;
        break;
    }
    case CONSTANT_FUNCTION:
        return(true);
    case COMPOSITION_OPERATION:
    {
        // Variáveis auxiliares:
        unsigned int i;
        bool retorno = true;
        // Nó auxilixar (necessário para chamar esta função recursivamente):
        NOfundef no_aux;
        no_aux.primitiva = false;
        no_aux.nome = NULL;
        no_aux.variaveis = NULL;
        no_aux.prox = NULL;
        // Fazer o cast do ponteiro da implementação:
        compositionimpl *impl = (compositionimpl*)no->implementacao.impl;
        // Tentar definir a função EXTERNA:
        no_aux.implementacao = impl->externa;
        if (!funlista_definir(fl,&no_aux))
        {
            ERRO_NAO_DECLARADA(funimpl_get_nome(impl->externa));
            retorno = false;
        }
        // Tentar definir cada função INTERNA:
        for (i=0 ; i<impl->internas_quant ; i++)
        {
            no_aux.implementacao = impl->internas[i];
            if (!funlista_definir(fl,&no_aux))
            {
                ERRO_NAO_DECLARADA(funimpl_get_nome(impl->internas[i]));
                retorno = false;
            }
        }
        return(retorno);
    }
    case RECURSION_OPERATION:
    {
        // Variável auxiliar:
        bool retorno = true;
        // Nó auxilixar (necessário para chamar esta função recursivamente):
        NOfundef no_aux;
        no_aux.primitiva = false;
        no_aux.nome = NULL;
        no_aux.variaveis = NULL;
        no_aux.prox = NULL;
        // Fazer o cast do ponteiro da implementação:
        recursionimpl *impl = (recursionimpl*)no->implementacao.impl;
        // Tentar definir o CASO BASE:
        no_aux.implementacao = impl->base;
        if (!funlista_definir(fl,&no_aux))
        {
            ERRO_NAO_DECLARADA(funimpl_get_nome(impl->base));
            retorno = false;
        }
        // Tentar definir o PASSO:
        no_aux.implementacao = impl->passo;
        if (!funlista_definir(fl,&no_aux))
        {
            ERRO_NAO_DECLARADA(funimpl_get_nome(impl->passo));
            retorno = false;
        }
        return(retorno);
    }
    default:
    {
        ERRO_TIPO_INVALIDO(__FUNCTION__,no->implementacao.tipo);
        return(false);
    }
    }
    // Agora, com os dados da implementação, buscar na lista o nó que ela define:
    NOfundef *busca = funlista_search(fl,fi_nome,fi_aridade);
    // Se não achou, então a função NÃO está DEFINIDA:
    if (!busca) return(false);
    // Setar o ponteiro "definicao" do nó e retornar sucesso:
    *ptr_fi_definicao = busca;
    return(true);
}
/// *** Funções sobre a cabeça da lista encadeada: [FIM] ***********************************************
